package com.LeeCode;

/**
 * 最大正方形
 */

public class Code221 {
    public static void main(String[] args) {
//        char[][] matrix = {{'1', '0', '1', '0', '0'},
//                {'1', '0', '1', '1', '1'},
//                {'1', '1', '1', '1', '1'},
//                {'1', '0', '0', '1', '0'}};
        char[][] matrix = {
                {'0', '0', '0', '1'},
                {'1', '1', '0', '1'},
                {'1', '1', '1', '1'},
                {'0', '1', '1', '1'},
                {'0', '1', '1', '1'},
        };

        System.out.println(new Code221().maximalSquare1(matrix));

    }

    public int maximalSquare1(char[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        int[][] dp = new int[rows][cols];
        int maxArea = 0;

        for (int i = 0; i < rows; i++) {
            dp[i][0] = matrix[i][0] == '1' ? 1 : 0;
            maxArea = Math.max(maxArea, dp[i][0]);
        }
        for (int i = 0; i < cols; i++) {
            dp[0][i] = matrix[0][i] == '1' ? 1 : 0;
            maxArea = Math.max(maxArea, dp[0][i]);
        }

        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (matrix[i][j] == '0') {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                }
                maxArea = Math.max(maxArea, dp[i][j]);
            }
        }
        return maxArea * maxArea;
    }

    public int maximalSquare(char[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        int[][] dp = new int[rows][cols];
        int maxArea = 0;

        for (int i = 0; i < rows; i++) {
            dp[i][0] = matrix[i][0] == '1' ? 1 : 0;
            maxArea = Math.max(maxArea, dp[i][0]);
        }
        for (int i = 0; i < cols; i++) {
            dp[0][i] = matrix[0][i] == '1' ? 1 : 0;
            maxArea = Math.max(maxArea, dp[0][i]);
        }

        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (matrix[i][j] == '0') {
                    dp[i][j] = 0;
                } else {
                    next(dp, i, j);
                }
                maxArea = Math.max(maxArea, dp[i][j]);
            }
        }
        return maxArea * maxArea;
    }

    public void next(int[][] dp, int x, int y) {
        int pre = dp[x - 1][y - 1];
        int row = 1, col = 1;
        for (int i = 1; i <= pre; i++) {
            if (dp[x][y - i] == 0) {
                break;
            }
            col++;
        }

        for (int i = 1; i <= pre; i++) {
            if (dp[x - i][y] == 0) {
                break;
            }
            row++;
        }
        dp[x][y] = Math.min(row, col);
    }
}
